package dynamic;

import java.util.Arrays;
/*
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

 网格中的障碍物和空位置分别用 1 和 0 来表示。



 示例 1：


输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右


 示例 2：


输入：obstacleGrid = [[0,1],[0,0]]
输出：1




 提示：


 m == obstacleGrid.length
 n == obstacleGrid[i].length
 1 <= m, n <= 100
 obstacleGrid[i][j] 为 0 或 1

 Related Topics 数组 动态规划 矩阵 👍 834 👎 0

*/

/**
 * @author luo
 * @description
 * @since 2022/7/19 15:06
 */
public class UniquePathsWithObstacles {

    int[][] cache;

    public static void main(String[] args) {
        int[][] obstacleGrid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        UniquePathsWithObstacles uniquePathsWithObstacles = new UniquePathsWithObstacles();
        int i = uniquePathsWithObstacles.uniquePathsWithObstacles(obstacleGrid);
        System.out.println(i);
        for (int j = 0; j < uniquePathsWithObstacles.cache.length; j++) {
            for (int k = 0; k < uniquePathsWithObstacles.cache[j].length; k++) {
                System.out.print(uniquePathsWithObstacles.cache[j][k]+"\t");
            }
            System.out.println();
        }
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        cache = new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int[] ints : cache) {
            Arrays.fill(ints, Integer.MIN_VALUE);
        }
        return find(0, 0, obstacleGrid);
    }

    public int find(int x, int y, int[][] obstacleGrid) {

        if (x >= obstacleGrid.length || y >= obstacleGrid[0].length) {
            return 0; // 超越数组的有效范围
        }
        int point = obstacleGrid[x][y];
        if (point == 1) {
//            障碍物
            return cache[x][y] = 0;
        }
        if (x == obstacleGrid.length - 1 && y == obstacleGrid[0].length - 1) {

            return cache[x][y]=1; // 抵达终点
        }
        int result = cache[x][y];
        if (result != Integer.MIN_VALUE) {
            return result;
        }

        int xPath = find(x + 1, y, obstacleGrid);
        int yPath = find(x, y + 1, obstacleGrid);
        return cache[x][y] = xPath + yPath;

    }
}
